package com.dataStructure.布隆过滤器;

public class BloomFilter<T> {
    /**
     * 二进制向量的长度(一共有多少位 二进制)
     */
    private int bitSize;

    /**
     * 二进制向量
     */
    private long[] bits;

    /**
     * 哈希函数的个数
     */
    private int hashSize;

    /**
     * @param n: 数据规模
     * @param p: 误判率
     */
    public BloomFilter(int n, double p) {
        if (n <= 0 || p <= 0 || p >= 1)
            throw new IllegalArgumentException("wrong n or p");

        double ln2 = Math.log(2);
        //求出二进制向量的长度
        bitSize = (int) (-(n * Math.log(p)) / (ln2 * ln2));
        //求哈希函数的个数
        hashSize = (int) (bitSize * ln2 / n);
        //初始化bits数组
        bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
    }

    /**
     * 添加元素
     * @param value
     * @return 是否成功新增
     */
    public boolean put(T value) {
        nullCheck(value);

        //利用value生成两个整数值
        int hash1 = value.hashCode();
        int hash2 = hash1 >>> 16;

        boolean result = false;
        for (int i = 0; i < hashSize; i++) {
            int combinedHash = hash1 + (i * hash2);
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            // 生成一个二进位的索引
            int index = combinedHash % bitSize;

            if (set(index)) result = true;
        }
        return result;
    }

    /**
     * 判断一个元素是否存在
     *
     * @param value
     * @return
     */
    public boolean contains(T value) {
        nullCheck(value);
        //利用value生成两个整数值
        int hash1 = value.hashCode();
        int hash2 = hash1 >>> 16;

        for (int i = 0; i < hashSize; i++) {
            int combinedHash = hash1 + (i * hash2);
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            // 生成一个二进位的索引
            int index = combinedHash % bitSize;
            //查询index位置的二进制位是否为0
            if (!get(index)) return false;
        }
        return true;
    }

    /**
     * 设置index位置的二进制位为1
     *
     * @param index
     * @return 是否成功设置进去，若为false，说明之前有其他值使这位变成1
     */
    private boolean set(int index) {
        //对应long数组的索引
        long value = bits[index / Long.SIZE];
        // 找到这个long的哪一位会设置为1
        int bitValue = 1 << (index % Long.SIZE);
        //将这个long的这一位设置为1
        bits[index / Long.SIZE] = value | bitValue;
        return (value & bitValue) == 0;
    }

    /**
     * 查看index位置的二进制位
     *
     * @param index
     * @return
     */
    private boolean get(int index) {
        long value = bits[index / Long.SIZE];
        return (value & 1L << (index % Long.SIZE)) != 0;
    }

    private void nullCheck(T value) {
        if (value == null)
            throw new IllegalArgumentException("value must not be null");
    }
}
